package com.atwulidun.dynamicprogramming03.knapsackproblem.unrefined;

import java.util.Arrays;

// 多重背包问题(未进行空间优化)
// 问题描述：
// 一共有N种物品，第i（i从1开始）种物品的数量为n[i]，重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
// 问题分析：
// 此时的分析和完全背包的分析二差不多，也是从装入第 i 种物品多少件出发：装入第i种物品0件、1件、...n[i]件（还要满足不超过限重）。
// 状态转移方程：
// # k为装入第i种物品的件数, k <= min(n[i], j/w[i])
// dp[i][j] = max{(dp[i-1][j − k*w[i]] + k*v[i]) for every k}
public class BoundedKnapsackProblem {
    // 物体的重量
    private static int[] w = {2, 4, 3};
    // 物体的价值
    private static int[] v = {500, 3000, 1000};
    // 物体的数量
    private static int[] n = {2, 1, 3};
    // 背包的最大容量
    private static int maxWeight = 12;
    // 前i个物体能装入背包容量为j时的最大价值
    // 行代表第几个物体，列代表背包的容量
    private static int[][] dp = new int[w.length + 1][maxWeight + 1];
    // 记录背包装入的物体，与dp维度相同
    private static int[][] path = new int[w.length + 1][maxWeight + 1];


    public static void main(String[] args) {
        // 对dp进行初始化，第一行和第一列全为0
        // 第一行置为0
        Arrays.fill(dp[0], 0);
        // 第一列置为0
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 0;
        }

        // 动态地将物品装入背包
        // 第一层循环控制物体
        for (int i = 1; i < dp.length; i++) {
            // 第二层循环控制背包容量
            for (int j = 1; j < dp[0].length ; j++) {
                // k == 0时
                int maxVal = dp[i - 1][j - 0 * w[i - 1]] + 0 * v[i - 1];
                // maxVal对应的k
                int maxK = 0;
                // 第三层循环控制当前物体的数量
                // 注意k的取值范围：k <= Math.min(n[i - 1], j/w[i - 1])
                for (int k = 1; k <= Math.min(n[i - 1], j/w[i - 1]); k++) {
                    if (dp[i - 1][j - k * w[i - 1]] + k * v[i - 1] > maxVal) {
                        maxVal = dp[i - 1][j - k * w[i - 1]] + k * v[i - 1];
                        maxK = k;
                    }
                }
                dp[i][j] = maxVal;
                // path存储的是maxVal对应的k的个数
                path[i][j] = maxK;
            }
        }

        // 对dp进行逆向遍历
        // 跟01背包的遍历很类似
        int i = path.length - 1;// 表示最后一件物体
        int j = path[0].length - 1;// 表示背包的最大容量
        while (i > 0 && j > 0) {
            // 如果背包的最大容量装入的是最后一件物体
            if (path[i][j] != 0) {
                int k = path[i][j];
                while (k > 0) {
                    System.out.println("第" + i + "件物品装入背包");
                    j -= w[i - 1];// 求出剩余的空间
                    k--;
                }
            }
            // 这里分两种情况：
            // 1.如果上面的if成立，那么i--是看剩余的空间是否装入了前一件物品
            // 2.如果上面的if不成立，那么i--是看当前空间是否装入了前一件物品
            i--;
        }
        for (int[] ints : dp) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
        for (int[] ints : path) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }
}
